Bitwise LMD GHOST
Resources
Validity Check of BitwiseGHOST
Verify the validity of block C3
https://gyazo.com/0e1646f8d18772519994b15d0932d53c
$ agreeing \lbrack h \rbrack: stores the number of votes consistent with block C3 upto height h in C3’s branch.
$ at \lbrack h \rbrack stores the number of votes that support exactly the block at height h in C3’s branch
Validity Check
Binary search in$ agreeing[\rbrackfor maximum height h where at least half of the validators agree.
Verify that $ 2 * agreeing[h+1\rbrack ≥ (agreeing[h\rbrack-at[h\rbrack)
Repeat for maximum height where at least a quarter of the validators agree, and verify the inequality. Next, repeat for maximum height where at least 1/8 of the validators agree, and so on. Continue until you reach the head.
Proof of correctness
Necessity is obvious.
Prove sufficiency by contradiction. Assume there exists$ h, s.t.
$ agreeing \lbrack h + 1 \rbrack < (agreeing \lbrack h \rbrack - at \lbrack h \rbrack) * 1/2 - ①
Let$ xbe the “current set of validators”
$ |V| / 2^{n + 1} < agreeing \lbrack h \rbrack < |V| / 2^n = x
$ agreeing \lbrack h \rbrack < x
From ①,
$ agreeing \lbrack h + 1 \rbrack < agreeing \lbrack h \rbrack * 1/2 < x/2
Therefore,$ his the largest height such that at least$ x/2agrees
This contradicts to ①
Proof with slacking for validator rotation
QUOTIENT = q
Assume towards contradiction
$ agreeing \lbrack h + 1 \rbrack < (agreeing \lbrack h \rbrack - at \lbrack h \rbrack) * h/q * 1/2 - ①
Let$ xbe the “current set of validators”
$ agreeing \lbrack h \rbrack < x
From ①,
$ agreeing \lbrack h + 1 \rbrack < agreeing \lbrack h \rbrack * h/q * 1/2 < h/q * x/2 < x/2
This contradicts to ①
(Without this proof, it is clear since the validity check with slacking is weaker than the normal validity check)
Bitwise-Tree
https://gyazo.com/5aa3aeb34a8104be150d9c97381d7fe1
mark all the children in original tree as descendants of B in the virtual tree
create virtual children
V0: have hash with prefix 0
V1: have hash with prefix 1
V0x: have hash with prefix 0x
V1x: have hash with prefix 1x
...
if the hash reaches a certain block in the original block, then replace that with the actual block
nrryuya.icon > Hash of what?
yudetamago.icon >
Basically it is just a "bits". About actual blocks, it represents something like a hash of block header.
Height in the Bitwise-Tree
Virtual height: 256 * original_height
yudetamago.icon > 256 is hash length
virtual agreement height:
the height up to which the block that their latest attestation pointed to agrees with the current chain
256 * actual_shared_height + number_of_common_bits
actual_shared_height: actual shared height in the original block tree
number_of_common_bits: initial common bits between
h: the depth of the block
LMD GHOST in the Bitwise-Tree
Mappings
last virtual agreement height
agrees_to[]: Validator -> Virtual height
last virtual agreement height for each validator
the virtual height up to which the block that v's latest attestation pointed to agrees with the current chain
last_agreeing[]: Virtual height -> Weight
mapping of virtual height to number of validators having that height as last agreement height
agreeing[]: Virtual height -> Weight
sum of the weights of the validators v where agrees_to[v] > h
last virtual at height
last_at[]: Validator -> Virtual height
last virtual at height for each validator
at[]: Virtual height -> Weight
how many validators’ latest messages signed exactly some block hash(?).
Updates
last_agreeing[]
update last_agreeing[] from it’s previous block when a new block is received
last_agreeing[agrees_to_perv[v]] - weight[v]
last_agreeing[agrees_to_new[v]] + weight[v]
The range of last_agreeing[] is h, which is the depth of the block
at[]
For each validator v, check if last_at[v] is equal to it’s last virtual agreement height.
If yes, then add the weight of the validator to at[last_at[v]].
This process will take $ O(V)
Queries
agreeing[]
agreeing[x] = last_agreeing[x] + … + last_agreeing[h]
Notes
segment tree
Why the binary tree is constructed by block root (hash)?
The construction of the tree must be deterministic for any set of child blocks because we cannot prove an inexistence of blocks
For any block hash, the child block with that hash can exist